#include <iostream>
#include <stdbool.h>
#include <assert.h>
using namespace std;
template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
	: _pLeft(nullptr)
	, _pRight(nullptr)
	, _pParent(nullptr)
	, _data(data)
	, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	AVLTree()
		: _pRoot(nullptr)
	{}

    // 在AVL树中插入值为data的节点
	bool Insert(const T& data)
    {
        if(_pRoot == nullptr)
        {
            _pRoot = new Node(data);
            return true;
        }
        Node* cur = _pRoot;
        Node* parent = nullptr;
        while(cur)
        {
            if(cur->_data < data)
            {
                parent = cur;
                cur = cur->_pRight;
            }
            else if(cur->_data > data)
            {
                parent = cur;
                cur = cur->_pLeft;
            }
            else if(cur->_data == data)
            {
                return false;
            }
        }
        cur = new Node(data);
        if(parent->_data > data)
        {
            parent->_pLeft = cur;
        }
        else if(parent->_data < data)
        {
            parent->_pRight = cur;
        }
        cur->_pParent = parent;
        while(parent)
        {
            if(parent->_pLeft == cur)
            {
                parent->_bf--;
            }
            else if(parent->_pRight == cur)
            {
                parent->_bf++;
            }
            if(parent->_bf == 0)
            {
                break;
            }
            else if(parent->_bf == -1 || parent->_bf == 1)
            {
                //向上调整平衡因子
                cur = parent;
                parent = parent->_pParent;
            }
            else if(parent->_bf == -2 || parent->_bf == 2)
            {
                //旋转
                if(parent->_bf == -2 && cur->_bf == -1)
                {
                    //纯粹的左边高,调右单旋
                    RotateR(parent);
                }
                else if(parent->_bf == 2 && cur->_bf == 1)
                {
                    //纯粹的右边高,调左单旋
                    RotateL(parent);
                }
                else if(parent->_bf == -2 && cur->_bf == 1)
                {
                    //左右双旋
                    RotateLR(parent);
                }
                else if(parent->_bf == 2 && cur->_bf == -1)
                {
                    //右左双旋
                    RotateRL(parent);
                }
                else
                {
                    assert(false);
                }
                break;
            }
            else
            {
                assert(false);
            }
        }
        return true;
    }
    
    // AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

private:
    // 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot)
    {
        if(pRoot == nullptr) return true;
        size_t leftHight = _Height(pRoot->_pLeft);
        size_t rightHight = _Height(pRoot->_pRight);
        int dicc = rightHight - leftHight;
        if(abs(dicc) >= 2)
        {
            cout << pRoot->_data << ":高度差异常" << endl;
            return false;
        }
        if(dicc != pRoot->_bf)
        {
            cout << pRoot->_data << ":平衡因子异常" << endl;
            return false;
        }
        return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
    }

	size_t _Height(Node* pRoot)
    {
        if(pRoot == nullptr) return 0;
        size_t leftHight = _Height(pRoot->_pLeft);
        size_t rightHight = _Height(pRoot->_pRight);
        return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
    }

    // 右单旋
	void RotateR(Node* pParent)
    {
        Node* subL = pParent->_pLeft;
        Node* subLR = subL->_pRight;
        Node* pphead = pParent->_pParent;
        subL->_pRight = pParent;
        pParent->_pLeft = subLR;
        if(subLR)
            subLR->_pParent = pParent;
        pParent->_pParent = subL;
        if(pParent == _pRoot)
        {
            _pRoot = subL;
            subL->_pParent = nullptr;
        }
        else
        {
            if(pphead->_pLeft == pParent)
            {
                pphead->_pLeft = subL;
            }
            else if(pphead->_pRight == pParent)
            {
                pphead->_pRight = subL;
            }
            subL->_pParent = pphead;
        }
        pParent->_bf = subL->_bf = 0;
    }

    // 左单旋
	void RotateL(Node* pParent)
    {
        Node* subR = pParent->_pRight;
        Node* subRL = subR->_pLeft;
        Node* pphead = pParent->_pParent;
        subR->_pLeft = pParent;
        pParent->_pRight = subRL;
        if(subRL)
            subRL->_pParent = pParent;
        pParent->_pParent = subR;
        if(pParent == _pRoot)
        {
            _pRoot = subR;
            subR->_pParent = nullptr;
        }
        else
        {
            if(pphead->_pLeft == pParent)
            {
                pphead->_pLeft = subR;
            }
            else if(pphead->_pRight == pParent)
            {
                pphead->_pRight = subR;
            }
            subR->_pParent = pphead;
        }
        pParent->_bf = subR->_bf = 0;
    }

    // 右左双旋
	void RotateRL(Node* pParent)
    {
        Node* subR = pParent->_pRight;
        Node* subRL = subR->_pLeft;
        int bf = subRL->_bf;
        RotateR(pParent->_pRight);
        RotateL(pParent);
        if(bf == 0)
        {
            pParent->_bf = 0;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else if(bf == 1)
        {
            pParent->_bf = -1;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else if(bf == -1)
        {
            pParent->_bf = 0;
            subR->_bf = 1;
            subRL->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }
    
    // 左右双旋
	void RotateLR(Node* pParent)
    {
        Node* subL = pParent->_pLeft;
        Node* subLR = subL->_pRight;
        int bf = subLR->_bf;
        RotateL(pParent->_pLeft);
        RotateR(pParent);
        if(bf == 0)
        {
            pParent->_bf = 0;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        else if(bf == -1)
        {
            pParent->_bf = 1;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        else if(bf == 1)
        {
            pParent->_bf = 0;
            subL->_bf = -1;
            subLR->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

private:
	Node* _pRoot;
};